//
//
//
//class Solution {
//    int maxSum = Integer.MIN_VALUE;
//
//    public int maxPathSum(TreeNode root) {
//        if (root == null) return 0;
//        getMaxSum(root);
//        return maxSum;
//    }
//
//
//    public int getMaxSum(TreeNode root) {
//        if (root == null) return 0;
//        int leftSum = Math.max(0, getMaxSum(root.left));
//        int rightSum = Math.max(0, getMaxSum(root.right));
//        int tmp = root.val + leftSum + rightSum;
//        maxSum = Math.max(maxSum, tmp);
//        return Math.max(leftSum, rightSum) + root.val;
//    }
//}